﻿using Digraphs;
using System;
using System.Collections.Generic;
using System.Text;

namespace ShortestPaths
{
    /// <summary>
    /// 基于拓扑的无环加权有向图的最短路径算法
    /// </summary>
    public class AcyclicSP
    {
        private DirectedEdge[] edgeTo;
        private double[] distTo;

        public AcyclicSP(EdgeWeightedDigraph G, int s)
        {
            edgeTo = new DirectedEdge[G.V()];
            distTo = new double[G.V()];

            for (var i = 0; i < G.V(); i++)
            {
                distTo[i] = Double.MaxValue;
            }
            distTo[0] = 0;

            Topological top = new Topological(G);
            foreach (var v in top.Order())
            {
                Relax(G,v);
            }
        }

        private void Relax(EdgeWeightedDigraph G, int v)
        {
            foreach (DirectedEdge e in G.Adj(v))
            {
                int w = e.To();
                if (distTo[w] > distTo[v] + e.Weight())
                {
                    distTo[w] = distTo[v] + e.Weight();
                    edgeTo[w] = e;
                }
            }
        }
    }
}
